#include "./sequential/include/mtf.h"
#include "huff.h"
#include "quicksort.h"
#include <string.h>
#include <stdio.h>
#include <math.h>

int verbose = 0;

int main(int argc, char** argv){
  unsigned char *string, *processed, *encrypted, *decrypted, *unprocessed;
  int length;
  string = "Hello, my name is Bob. Nice to meet you!bqskhchdvcsmnnbdkjwcbedkwjabc ccccccccccccccccccccccccccccbbbbbbbbbwiugbfcw;qkgbckjbdicgbl;wkjbasdioudf3bwiubkjdbskcuehwb	;qbhwekdckjsbdiuwjdbsb,mnm,m,noilkjlknuiog75e35qaweAZfgvb cjbomkhugd8237`4678gedijnalmp03i-  -d -2uj90xnm2e03yehd2908jpk-0uij09uh76r4wse5sxf 1k2mp[sk'q,'qk-d0=2pld[','ak[ok";
  length = strlen(string);
  processed = malloc(length*sizeof(unsigned char));
  memset(processed, 0, length*sizeof(unsigned char));
  encrypted = malloc(3*length*sizeof(unsigned char));
  memset(encrypted, 0, 3*length*sizeof(unsigned char));
  decrypted = malloc(length*sizeof(unsigned char));
  memset(decrypted, 0, length*sizeof(unsigned char));
  unprocessed = malloc(length*sizeof(unsigned char));
  memset(unprocessed, 0, length*sizeof(unsigned char));
  verbose = 1;

  mtfencode(processed, string, length);
  huffencode(encrypted, processed, length);
  huffdecode(decrypted, encrypted);
  mtfdecode(unprocessed, decrypted, length);

  printf("%s\n%s\n%s\n%s\n%s\n", string, processed, encrypted, decrypted, unprocessed);
}

int huffencode(unsigned char* dst, unsigned char* src, int length){
  int i, j;
  Node table[256], *root, *go, *tree = malloc(sizeof(Node)), *first = tree;
  tree->value = 0;
  tree->prob = 0;
  tree->left = NULL;
  tree->right = NULL;
  tree->next = NULL;
  for(i = 0; i < 256; i++){
    table[i].value = i;
    table[i].prob = 0;
  }
  for(i = 0; i < length; i++)
    (table[src[i]].prob)++;
  sort(table, 0, 256);
  i = 0;
  while(table[i].prob == 0) i++;
  for(i; i < 256-1; i++){
    /*for(go = first; ; go = (Node*)go->next){
      printf("%d %d %d %d %d\n", go->value, go->prob, go, go->left, go->right);
      if(go->next == NULL) break;
    }
    printf("%d %d %d %d\n", table[i].value, table[i].prob, table[i+1].value, table[i+1].prob);
    printf("\n");
    getchar();*/
    Node *l, *r;
    if(table[i].value != NaB){
      tree->value = table[i].value;
      tree->prob = table[i].prob;
      tree->left = NULL;
      tree->right = NULL;
      l = tree;
      tree->next = malloc(sizeof(Node));
      tree = (Node*)tree->next;
    }
    else
      l = (Node*)table[i].next;
    if(table[i+1].value != NaB){
      tree->value = table[i+1].value;
      tree->prob = table[i+1].prob;
      tree->left = NULL;
      tree->right = NULL;
      r = tree;
      tree->next = malloc(sizeof(Node));
      tree = (Node*)tree->next;
    }
    else
      r = (Node*)table[i+1].next;
    tree->value = NaB;
    tree->prob = l->prob+r->prob;
    tree->right = (void*)r;
    tree->left = (void*)l;
    tree->next = NULL;
    if(i < 254){
      tree->next = malloc(sizeof(Node));
      table[i+1].value = NaB;
      table[i+1].prob = (l->prob)+(r->prob);
      table[i+1].next = (void*)tree;
      tree = (Node*)tree->next;
      tree->value = 0;
      tree->prob = 0;
      tree->left = NULL;
      tree->right = NULL;
      tree->next = NULL;
      sort(table, i+1, 256);
    }
    else
      root = tree;
  }
  int dstloc = 0;
  setcodes(root, 0, 0, dst, 1, &dstloc);
  int treelen = dstloc;
  dst[treelen++] = 255;
  dst[treelen++] = 255;
  
  /*for(go = first; ; go = (Node*)go->next){
    printf("%d %d %d %d %d\n", go->value, go->prob, go, go->left, go->right);
    if(go->next == NULL) break;
  }*/

  int bitlen = 0;
  char c = 0;
  for(i = 0; i < length; i++){
    Node* n = findcode(root, src[i]);
    //printf("Found character '%c' with code '%d'\n", n->value, n->prob);
    for(j = 0; j < n->length; j++){
      if((bitlen%8) == 0)
        c = 0;
      char temp = (n->prob >> (n->length  - j - 1)) & 1;
      c = (c << 1) + temp;
      if((bitlen%8) == 7){
        dst[treelen+bitlen/8] = c;
        //printf("Wrote byte '%d' with '%d'\n", bitlen/8, c);
      }
      bitlen++;
    }
    //printf("%d\n", bitlen);
  }
  if(c != 0){
    c = c << (8 - (bitlen%8));
    dst[treelen+bitlen/8] = c;
  }
  dst[treelen-1] = (char)(bitlen/8 + 1);
}

int huffdecode(unsigned char* dst, unsigned char* src){
  int i, j, k, min = pow(2, 31)-1;
  Element *list = malloc(sizeof(Element)), *element;
  element = list;
  for(i = 0; src[i] != 255; i=i+3){
    element->value = src[i];
    element->pos = 0;
    element->pos += src[i+1]<<8;
    element->pos += src[i+2];
    if(element->pos < min) min = element->pos;
    printf("%d\n", element->pos);
    element->next = malloc(sizeof(Element));
    element = (Element*)element->next;
  }
  int size = i + src[++i];
  printf("%d\n", size);
  int c = 1;
  k = 0;
  for(i = i+1; i <= size; i++){
    for(j = 7; j >= 0; j--){
      c = (c<<1) + ((src[i]>>j)&1);
      element = list;
      while(element->next != NULL){
        if((int)element->pos == (int)c){
          dst[k++] = element->value;
          printf("%c\n", dst[k-1]);
          c = 1;
          break;
        }
        element = (Element*)element->next;
      }
    }
  }
  dst[k] = 0;
}

int setcodes(Node *root, int l, int code, unsigned char* dst, int pos, int* dstloc){
  if(root->value != NaB){
    root->prob = code;
    root->length = l;
    dst[(*dstloc)++] = root->value;
    dst[(*dstloc)++] = (unsigned char)(pos>>8);
    dst[(*dstloc)++] = (unsigned char)pos;
    printf("%c\t%d\t%d\t%d\t%d\n", root->value, root->value, root->prob, root->length, pos);
  }
  if(root->left != NULL)
    setcodes((Node*)root->left, l+1, code<<1, dst, 2*pos, dstloc);
  if(root->right != NULL)
    setcodes((Node*)root->right, l+1, (code<<1) + 1, dst, 2*pos+1, dstloc);
}

Node* findcode(Node *root, char c){
  Node* n = NULL;
  if(root->value == c){
    //printf("%c\n", c);
    return root;
  }
  if(root->left != NULL){
    n = findcode((Node*)root->left, c);
    if(n!=NULL) return n;
  }
  if(root->right != NULL)
    n = findcode((Node*)root->right, c);
  return n;
}
